# 面试题 17.05.  字母与数字

# 给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

# 返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

# 示例 1:

# 输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

# 输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
# 示例 2:

# 输入: ["A","A"]

# 输出: []
# 提示：

# array.length <= 100000


# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/find-longest-subarray-lcci
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


from time import time
from typing import List


class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        dic,count,start,end={0:0},0,0,0
        for i in range(len(array)):
            count+=1 if array[i].isdigit() else -1
            if count in dic:
                a=dic[count]
                if i+1-a>end-start:
                    start,end=a,i+1
            else:
                dic[count]=i+1
        return array[start:end]
    
    
if __name__ == '__main__':
    args = {"array": ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]}
    start = time()
    print(Solution().findLongestSubarray(**args))
    print('='*40)
    print('耗时:', time()*1000 - start*1000, 'ms')